package class11;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/minimum-cost-for-tickets/
 * 最低票价问题
 */
public class Code02_MincostTickets {
    // 无论提交什么方法，都带着这个数组    0  1  2
    public static int[] durations = {1, 7, 30};

    public static void main(String[] args) {
        int[] days = {1, 4, 6, 7, 8, 20};
        int[] costs = {2, 7, 15};

        int i = mincostTickets1(days, costs);
        System.out.println("i = " + i);

        int i1 = mincostTickets2(days, costs);
        System.out.println("i1 = " + i1);
    }

    // 暴力尝试
    public static int mincostTickets1(int[] days, int[] costs) {
        return f1(days, costs, 0);
    }

    /**
     * i为下标，默认从0开始
     * days:为旅行天
     * day[i......最少花费多少
     */
    public static int f1(int[] days, int[] costs, int i) {
        // 当i越界试试，表示后续已经无旅行
        if (i == days.length) return 0;

        // i下标：第days[i]天，有一场旅行
        // ans 是计算金额
        int ans = Integer.MAX_VALUE;
        // k表示同行类型
        // 0:1天
        // 1:7天
        // 2:30天
        for (int k = 0, j = i; k < 3; k++) {
            // j < days.length: 下一个有效天的下标
            // days[i]:当天数
            // durations[k]:有效天数
            // days[j]: 下一个旅行天
            // days[i] + durations[k] > days[j]: 如果当前天+票的有效期 > 下一个旅行天，则j++
            while (j < days.length && days[i] + durations[k] > days[j]) {
                j++;
            }
            // 1.循环跳出，表示当前票的有效期，已经无法对 day[j]天有效了
            // 2.此时，costs[k]为当前的金额 + 下一个旅行天j开始的金额
            ans = Math.min(ans, costs[k] + f1(days, costs, j));
        }
        System.out.println();
        return ans;
    }

    public static int mincostTickets2(int[] days, int[] costs) {
        int[] dp = new int[days.length];
        for (int i = 0; i < days.length; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        return f2(days, costs, 0, dp);
    }

    private static int f2(int[] days, int[] costs, int i, int[] dp) {
        if (i == days.length) {
            return 0;
        }
        if (dp[i] != Integer.MAX_VALUE) {
            return dp[i];
        }
        int ans = Integer.MAX_VALUE;
        for (int k = 0, j = i; k < 3; k++) {
            while (j < days.length && days[i] + durations[k] > days[j]) {
                j++;
            }
            ans = Math.min(ans, costs[k] + f2(days, costs, j, dp));
        }
        dp[i] = ans;
        return ans;
    }

    public static int MAXN = 366;

    public static int mincostTickets3(int[] days, int[] costs) {
        int[] dp = new int[MAXN];
        int n = days.length;
        Arrays.fill(dp, 0, n + 1, Integer.MAX_VALUE);
        dp[n] = 0;
        for (int i = n - 1; i >= 0; i--) {
            for (int k = 0, j = i; k < 3; k++) {
                while (j < days.length && days[i] + durations[k] > days[j]) {
                    j++;
                }
                dp[i] = Math.min(dp[i], costs[k] + dp[j]);
            }
        }
        return dp[0];
    }
}
